package top.pro51.guide.chapter1;


import java.util.Stack;

class 用栈来求解汉诺塔问题2 {
    public enum Action {
        No, LeftToMid, MidToLeft, MidToRight, RrghtToMid
    }

    //这里造一个全局的变量用于传引用  代替原代码的数组传引用   这样写不行啊。。。。。
    //private static Action record = Action.No;

    public static int hanoiProblem2(int num, String left, String mid, String right) {
        Action[] record = {Action.No};
        //左栈
        Stack<Integer> LS = new Stack<Integer>();
        //中栈
        Stack<Integer> MS = new Stack<Integer>();
        //右栈
        Stack<Integer> RS = new Stack<Integer>();
        LS.push(Integer.MAX_VALUE);
        MS.push(Integer.MAX_VALUE);
        RS.push(Integer.MAX_VALUE);
        //从num开始由大到小依次入左栈
        for (int i = num; i > 0; i--) {
            LS.push(i);
        }
        int step = 0;
        //如果右栈的个数不等于num+1说明还没有移动完
        while (RS.size() != num + 1) {
            step += fStackTotStack(record, Action.MidToLeft, Action.LeftToMid, LS, MS, left, mid);
            step += fStackTotStack(record, Action.LeftToMid, Action.MidToLeft, MS, LS, mid, left);
            step += fStackTotStack(record, Action.RrghtToMid, Action.MidToRight, MS, RS, mid, right);
            step += fStackTotStack(record, Action.MidToRight, Action.RrghtToMid, RS, MS, right, mid);
        }
        return step;
    }

    /**
     * 判断从栈 fStack 的栈顶移动到 tStack 是否可行，可行则移动
     *
     * @param preNoAct 当前动作不允许的前置动作
     * @param nowAct   当前动作
     * @param fStack   来源栈
     * @param tStack   目标栈
     * @param from     来源位置
     * @param to       目标位置
     * @return
     */
    public static int fStackTotStack(Action[] record, Action preNoAct, Action nowAct,
                                     Stack<Integer> fStack, Stack<Integer> tStack,
                                     String from, String to) {
        // 判断前一个方法是否当前方法的互逆方法，不是的话，方可执行；
        // 判断来源的栈顶和目标的栈顶孰大孰小，必须满足小顶压入大顶
        if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
            tStack.push(fStack.pop());
            System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
            record[0] = nowAct;
            return 1;
        }
        return 0;
    }
}
